package Day18;

/**
 * ------------------------------------------------------------------------------------
 * 题目：
 *      几乎每一个人都用乘法表。但是你能在乘法表中快速找到第k小的数字吗？
 *      给定高度m、宽度n 的一张m * n的乘法表，以及正整数k，你需要返回表中第k小的数字。
 * ------------------------------------------------------------------------------------
 * 示例：
 *      输入: m = 3, n = 3, k = 5
 *      输出: 3
 *      解释:
 *          乘法表:
 *                 1   2   3
 *                 2   4   6
 *                 3   6   9
 *          第5小的数字是 3 (1, 2, 2, 3, 3).
 * -----------------------------------------------------------------------------------
 * 方法：
 *      二分查找
 * -----------------------------------------------------------------------------------
 */
class Solution {
    public static void main(String[] args) {
        System.out.println(findKthNumber(3,3,5));
    }
    public static int findKthNumber(int m, int n, int k) {
        int left = 1;
        int right = m*n;
        while(left<right){
            int mid = (left+right)>>1;
            if(count(m,n,mid)<k){
                left=mid+1;
            }else{
                right=mid;
            }
        }
        return left;
    }
    public static int count(int m,int n,int x){
        int i=m;
        int j=1;
        int ans=0;
        while(i >= 1 && j <= n){
            if(i*j<=x){
                ans += i;
                ++j;
            }else{
                --i;
            }
        }
        return ans;
    }
}